#include "stack_queue.h"
#include <vector>

listNode::listNode() : data(0), next(NULL) {}
listNode::listNode(int nodeData, listNode* succ) : data(nodeData), next(succ) {}

void MyStack::printStack(){
    listNode* p = topNode;
    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";
        p = p->next;
    }
}

void MyQueue::printQueue(){
    int cursor = front;
    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";
        cursor = (cursor + 1) % capacity;
    }
}

MyStack::MyStack(): topNode(NULL), stackSize(0){}

MyStack::~MyStack()
{
    listNode* temp;
    while(topNode != NULL){
        temp = topNode;
        topNode = topNode->next;
        delete temp;
    }
    stackSize = 0;
}

bool MyStack::push(const int& data)
{
    listNode* newNode = new listNode(data, topNode);
    if(newNode == NULL) return false;
    topNode = newNode;
    stackSize++;
    return true;
}

bool MyStack::pop(int& item)
{
    if(topNode == NULL)return false;
    listNode* temp = topNode;
    item = temp->data;
    topNode = topNode->next;
    delete temp;
    stackSize--;
    return true;
}

bool MyStack::getTop(int& item)
{
    if(topNode == NULL)return false;
    item = topNode->data;
    return true;
}

MyQueue::MyQueue(const int& cap) : capacity(cap), front(0), rear(0) {
    queue = new int[capacity];
}

MyQueue::~MyQueue() {
    delete[] queue;
}

bool MyQueue::isFull() {
    return (rear + 1) % capacity == front;
}

bool MyQueue::enQueue(const int& data)
{
    if (isFull()) return false;
    queue[rear] = data;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int& item) {
    if (front == rear) return false;
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& item) {
    if (front == rear) return false;
    item = queue[front];
    return true;
}

bool isOperator(int op) {
    char c = (char)op;
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int getPriority(int op) {
    char c = (char)op;
    if (c == '(') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return 0;
}

bool postfixExpression(const string& infix, string& result) {
    MyStack opStack;
    result.clear();
    int len = infix.size();
    for (int i = 0; i < len; i++) {
        char c = infix[i];
        if (c >= '0' && c <= '9') {
            result += c;
        }
        else if (c == '(') {
            opStack.push((int)c);
        }
        else if (c == ')') {
            int topOp;
            bool findLeft = false;
            while (opStack.getTop(topOp)) {
                opStack.pop(topOp);
                if ((char)topOp == '(') {
                    findLeft = true;
                    break;
                }
                result += (char)topOp;
            }
            if (!findLeft) { result = "Expression is wrong!"; return false; }
        }
        else if (isOperator((int)c)) {
            bool leftValid = false;
            bool rightValid = false;
            if (i > 0) {
                char leftChar = infix[i-1];
                leftValid = (leftChar >= '0' && leftChar <= '9') || (leftChar == ')');
            }
            if (i < len - 1) {
                char rightChar = infix[i+1];
                rightValid = (rightChar >= '0' && rightChar <= '9') || (rightChar == '(');
            }
            if (i == 0 || i == len - 1 || !leftValid || !rightValid) {
                result = "Expression is wrong!";
                return false;
            }
            int topOp;
            while (opStack.getTop(topOp)) {
                if (getPriority(topOp) >= getPriority((int)c) && (char)topOp != '(') {
                    opStack.pop(topOp);
                    result += (char)topOp;
                } else {
                    break;
                }
            }
            opStack.push((int)c);
        }
        else {
            result = "Expression is wrong!";
            return false;
        }
    }
    int topOp;
    while (opStack.pop(topOp)) {
        if ((char)topOp == '(') {
            result = "Expression is wrong!";
            return false;
        }
        result += (char)topOp;
    }
    return true;
}

bool expressionVal(const string& postfix, int& result) {
    MyStack numStack;
    result = 0;
    int len = postfix.size();
    for (int i = 0; i < len; i++) {
        char c = postfix[i];
        if (c >= '0' && c <= '9') {
            numStack.push(c - '0');
        }
        else if (isOperator((int)c)) {
            int rightVal, leftVal;
            if (!numStack.pop(rightVal)) { return false; }
            if (!numStack.pop(leftVal)) { return false; }
            switch (c) {
                case '+': result = leftVal + rightVal; break;
                case '-': result = leftVal - rightVal; break;
                case '*': result = leftVal * rightVal; break;
                case '/': 
                    if (rightVal == 0) { return false; }
                    result = leftVal / rightVal; break;
                default: return false;
            }
            numStack.push(result);
        }
        else { return false; }
    }
    if (!numStack.pop(result)) { return false; }
    if (numStack.getTop(result)) { return false; }
    return true;
}

void yanghui(const int& n) {
    MyQueue q(100);
    q.enQueue(1);
    q.enQueue(1);
    for (int line = 1; line <= n; line++) {
        vector<int> currLine;
        int size = line + 1;
        for (int j = 0; j < size; j++) {
            int curr;
            q.deQueue(curr);
            currLine.push_back(curr);
        }
        for (int j = 0; j < size; j++) {
            if (j > 0) cout << ",";
            cout << currLine[j];
        }
        cout << endl;
        for (int j = 0; j < size + 1; j++) {
            if (j == 0 || j == size) q.enQueue(1);
            else q.enQueue(currLine[j-1] + currLine[j]);
        }
    }
}